import java.util.PriorityQueue;

/**
 * @ClassName Offer25
 * @Description 剑指 Offer 25. 合并两个排序的链表
 * @Author clockTown
 * @Date 2021/8/23 8:50
 * @Version 1.0
 */
class Offer25 {
}

/**
 * v0 优先队列
 */
class Offer25V0 {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>((o1, o2) -> (o1.val - o2.val));
        while (l1 != null){
            priorityQueue.offer(l1);
            l1 = l1.next;
        }
        while (l2 != null){
            priorityQueue.offer(l2);
            l2 = l2.next;
        }

        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while (!priorityQueue.isEmpty()){
            cur.next = priorityQueue.poll();
            cur = cur.next;
        }
        cur.next = null;
        return dummy.next;
    }
}

/**
 * v1 双指针
 */
class Offer25V1 {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null){
            return l1 == null ? l2: l1;
        }

        ListNode dummy = new ListNode(-1);
        ListNode head = dummy;

        while (l1 != null && l2 != null){
            if (l1.val < l2.val){
                head.next = l1;
                l1 = l1.next;
            }else {
                head.next = l2;
                l2 = l2.next;
            }
            head = head.next;
        }
        head.next = (l1 != null) ? l1:l2;
        return dummy.next;
    }
}

/**
 * v2 递归
 */
class Offer25V2 {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) {
            return l2;
        }
        if(l2 == null) {
            return l1;
        }
        if(l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}
